package com.jinan.algorithm.binaryTree;

import com.jinan.common.TreeNode;

import java.util.*;

public class RecursionTest {
    public static void main(String[] args) {

    }

    /**
     * 104. 二叉树的最大深度 <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/">...</a>
     * 难度: 简单
     * tag: 递归
     * description:
     * 给定一个二叉树，找出其最大深度。
     *
     * @param root 二叉树根节点
     * @return int 二叉树的最大深度
     */
    public int maxDepth(TreeNode<Integer> root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 100. 相同的树 <a href="https://leetcode.cn/problems/same-tree/description/">...</a>
     * 难度: 简单
     * tag: 递归
     * description:
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * @param p 二叉树1
     * @param q 二叉树2
     * @return boolean 是否相同
     */
    public boolean isSameTree(TreeNode<Integer> p, TreeNode<Integer> q) {
        if (p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /**
     * 101. 对称二叉树 <a href="https://leetcode.cn/problems/symmetric-tree/description/">...</a>
     * 难度: 简单
     * tag: 递归
     * description:
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     *
     * @param root 二叉树根节点
     * @return boolean 是否对称
     */
    public boolean isSymmetric(TreeNode<Integer> root) {
        if (root == null) {
            return true;
        }
        return isSameTree2(root.left, root.right);
    }

    public boolean isSameTree2(TreeNode<Integer> p, TreeNode<Integer> q) {
        if (p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
    }

    /**
     * 110. 平衡二叉树 <a href="https://leetcode.cn/problems/balanced-binary-tree/description/">...</a>
     * 难度: 简单
     * tag: 递归
     * description:
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     *
     * @param root 二叉树根节点
     * @return boolean 是否平衡
     * @apiNote 思路：求高度，递归求左右子树的高度，高度差不超过1
     */
    public boolean isBalanced(TreeNode<Integer> root) {
        int height = getHeight(root);
        return height != -1;
    }

    public int getHeight(TreeNode<Integer> root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 199. 二叉树的右视图 <a href="https://leetcode.cn/problems/binary-tree-right-side-view/description/">...</a>
     * 难度: 简单
     * tag: 递归
     * description:
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * @param root 二叉树根节点
     * @return List<Integer>右侧节点值
     * @apiNote 思路：递归，从右子树开始，遍历，记录高度，高度相同则替换
     */
    public List<Integer> rightSideView(TreeNode<Integer> root) {
        List<Integer> result = new ArrayList<>();
        rightSideView(root, 0, result);
        return result;
    }

    public void rightSideView(TreeNode<Integer> root, int deep, List<Integer> result) {
        if (root == null) {
            return;
        }
        if (deep == result.size()) {
            result.add(root.val);
        }
        rightSideView(root.right, deep + 1, result);
        rightSideView(root.left, deep + 1, result);
    }

    /**
     * 98. 验证二叉搜索树 <a href="https://leetcode.cn/problems/validate-binary-search-tree/description/">...</a>
     * 难度: 简单
     * tag: 递归
     * description:
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * 有效 二叉搜索树定义如下：
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     *
     * @param root 二叉树根节点
     * @return boolean 是否有效
     * @apiNote 思路：递归，中序遍历，判断是否递增
     */
    public boolean isValidBST(TreeNode<Integer> root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 前序遍历
    public boolean isValidBST(TreeNode<Integer> root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }

    // 中序遍历
    private Long pre = null;

    public boolean isValidBST2(TreeNode<Integer> root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST2(root.left)) {
            return false;
        }
        if (pre != null && root.val <= pre) {
            return false;
        }
        pre = Long.valueOf(root.val);
        return isValidBST2(root.right);
    }

    // 后序遍历
    public boolean isValidBST3(TreeNode<Integer> root) {
        return dfs(root)[1] != Long.MAX_VALUE;
    }

    private long[] dfs(TreeNode<Integer> node) {
        if (node == null) {
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        }
        long[] left = dfs(node.left);
        long[] right = dfs(node.right);
        long x = node.val;
        // 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
        if (x <= left[1] || x >= right[0]) {
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        }
        return new long[]{Math.min(left[0], x), Math.max(right[1], x)};
    }

    /**
     * 236. 二叉树的最近公共祖先 <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/">...</a>
     * 难度: 中等
     * tag: 递归
     * description:
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先
     * 并且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * @param root 二叉树根节点
     * @param p    节点p
     * @param q    节点q
     * @return 最近公共祖先
     * @apiNote 思路：递归，判断p和q是否在root的子树中，如果在，则root为最近公共祖先,否则在左子树或右子树中找
     */
    public TreeNode<Integer> lowestCommonAncestor(TreeNode<Integer> root, TreeNode<Integer> p, TreeNode<Integer> q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode<Integer> left = lowestCommonAncestor(root.left, p, q);
        TreeNode<Integer> right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    /**
     * 235. 二叉搜索树的最近公共祖先 <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/">...</a>
     * 难度: 中等
     * tag: 递归
     * description:
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 节点节点值都是唯一的。
     *
     * @param root 二叉树根节点
     * @param p    节点p
     * @param q    节点q
     * @return 最近公共祖先
     */
    public TreeNode<Integer> lowestCommonAncestor2(TreeNode<Integer> root, TreeNode<Integer> p, TreeNode<Integer> q) {
        Integer val = root.val;
        if (val > p.val && val > q.val) {
            return lowestCommonAncestor2(root.left, p, q);
        }
        if (val < p.val && val < q.val) {
            return lowestCommonAncestor2(root.right, p, q);
        }
        return root;
    }

    /**
     * 102. 二叉树的层序遍历 <a href="https://leetcode.cn/problems/binary-tree-level-order-traversal/description/">...</a>
     * 难度: 简单
     * tag: 树 广度优先搜索 二叉树
     * description:
     * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     * restrictions:
     * 树中节点数目在范围 [0, 2000] 内
     * -100 <= Node.val <= 100
     *
     * @param root 二叉树根节点
     * @return ans 二叉树按层序遍历得到的节点值
     * @apiNote 思路：递归，广度优先遍历，队列
     */
    public List<List<Integer>> levelOrder(TreeNode<Integer> root) {
        // 结果集
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        // 队列
        Deque<TreeNode<Integer>> queue = new LinkedList<>();
        // 根节点入队
        queue.add(root);
        // 当队列不为空，则将本层的节点值加入结果集，并将下一层的节点入队
        while (!queue.isEmpty()) {
            // 当前层节点值
            List<Integer> vals = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode<Integer> node = queue.removeFirst();
                vals.add(node.val);
                // 左右子树不为空入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 将本层的节点值加入结果集
            ans.add(vals);
        }
        return ans;
    }

    /**
     * 103. 二叉树的锯齿形层序遍历 <a href="https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/">...</a>
     * 难度: 中等
     * tag: 树 广度优先搜索 二叉树
     * description:
     * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。 （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     * restrictions:
     * 树中节点数目在范围 [0, 2000] 内
     * -100 <= Node.val <= 100
     *
     * @param root 二叉树根节点
     * @return ans 二叉树按锯齿形层序遍历得到的节点值
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode<Integer> root) {
        // 结果集
        List<List<Integer>> ans = new ArrayList<>();
        // 如果根节点为空，则返回空结果集
        if (root == null) {
            return ans;
        }
        // 队列
        Deque<TreeNode<Integer>> queue = new LinkedList<>();
        // 根节点入队
        queue.add(root);
        // 当队列不为空，则将本层的节点值加入结果集，并将下一层的节点入队
        while (!queue.isEmpty()) {
            List<Integer> vals = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode<Integer> node = queue.removeFirst();
                vals.add(node.val);
                //双端队列写法
                // 如果ans的层数为奇数，则将当前节点的值添加到双端队列的开头，否则添加到双端队列的末尾
//                if (ans.size() % 2 == 1) {
//                    vals.addFirst(node.val);
//                } else {
//                    vals.addLast(node.val);
//                }
                // 左右子树不为空入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 如果ans的层数为奇数，则将vals反转
            if (ans.size() % 2 == 1) {
                Collections.reverse(vals);
            }
            // 将本层的节点值加入结果集
            ans.add(vals);
        }
        return ans;
    }

    /**
     * 513. 找树左下角的值 <a href="https://leetcode.cn/problems/find-bottom-left-tree-value/description/">...</a>
     * 难度: 中等
     * tag: 树 深度优先搜索 二叉树
     * description:
     * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
     * 假设二叉树中至少有一个节点。
     * restrictions:
     * 树中节点数目在范围 [1, 104] 内
     * -2^31 <= Node.val <= 2^31 - 1
     *
     * @param root 二叉树根节点
     * @return ans 最底层最左边节点的值
     * @apiNote 思路：广度优先遍历，每层从右到左遍历，最后一层的最后一个节点就是最底层 最左边 的节点
     * 或者递归，深度优先遍历，记录当前层数，并记录当前层最小的节点值
     */
    public int findBottomLeftValue(TreeNode<Integer> root) {
        Deque<TreeNode<Integer>> queue = new LinkedList<>();
        TreeNode<Integer> node = null;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                node = queue.removeFirst();
                // 左右子树不为空入队,先入队右子树，再入队左子树
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
            }
        }
        // 最后一层的最后一个节点就是最底层 最左边 的节点
        return node.val;
    }

    // 左视图，递归
//    public int findBottomLeftValue2(TreeNode<Integer> root) {
//        // ans 每层第一个遍历到节点的值
//        List<Integer> ans = new ArrayList<>();
//        leftReview(root, 0, ans);
//        return ans.getLast();
//    }

    private void leftReview(TreeNode<Integer> root, int deep, List<Integer> ans) {
        if (root == null) {
            return;
        }
        // 当前层数等于结果集的长度，则将当前节点的值加入结果集
        if (deep == ans.size()) {
            ans.add(root.val);
        }
        leftReview(root.left, deep + 1, ans);
        leftReview(root.right, deep + 1, ans);
    }

    /**
     * 226. 翻转二叉树 <a href="https://leetcode.cn/problems/invert-binary-tree/description/">...</a>
     * 难度: 简单
     * tag: 树 深度优先搜索 广度优先搜索 二叉树
     * description:
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * restrictions:
     * 树中节点数目范围在 [0, 100] 内
     * -100 <= Node.val <= 100
     * @param root 二叉树根节点
     * @return ans 翻转二叉树的根节点
     * @apiNote 思路：递归，交换左右子树
     */
    public TreeNode<Integer> invertTree(TreeNode<Integer> root) {
        if(root == null){
            return null;
        }
        TreeNode<Integer> left = invertTree(root.left);
        TreeNode<Integer> right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    /**
     * 94. 二叉树的中序遍历 <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/description/">...</a>
     * 难度: 简单
     * tag: 树 深度优先搜索 二叉树
     * description:
     * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
     * restrictions:
     * 树中节点数目在范围 [0, 100] 内
     * -100<= Node.val <= 100
     * @param root 二叉树根节点
     * @return ans 二叉树的中序遍历
     * @apiNote 思路：递归，中序遍历 左根右
     */
    public List<Integer> inorderTraversal(TreeNode<Integer> root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }

    private void inorder(TreeNode<Integer> root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
    }
}
